package com.bclz.al.linlist

import com.bclz.al.dynamic.List

class LinkedList[T]() extends List[T] {

  case class Node[T](var ele:T,var next:Node[T])

  var n:Node[T]=null
  var size0=0

  /**
    * 大小
    *
    * @return
    */
  override def size(): Int = size0

  /**
    * 是否为空
    *
    * @return
    */
  override def isEmpty(): Boolean = size0==0

  /**
    * 添加
    * O(n)
    * @param ele
    */
  override def add(ele: T): Unit = {
    val eleNode=Node[T](ele,null)
    if(n!=null){
      var currentN=n
      while(currentN.next!=null) currentN=currentN.next
      currentN.next=eleNode
    }else{
      n=eleNode
    }
    size0+=1
  }

  override def add(ele: T, index: Int): Unit = {
    rangeCheckForAdd(index)
    val eleNode=Node[T](ele,null)
    if(index==0){
      eleNode.next=n
      n=eleNode
    }else{
      val lastNode = findNode(index-1)
      val oldNext = lastNode.next
      eleNode.next=oldNext
      lastNode.next=eleNode
    }
    size0+=1

  }

  override def set(ele: T, index: Int): T = {
    rangeCheck(index)
    val currentN=findNode(index)
    val oldEle=currentN.ele
    currentN.ele=ele
    oldEle
  }

  def findNode(index:Int):Node[T]={
    var lastN:Node[T]=Node[T](null.asInstanceOf[T],n)
    for (_ <- (0 to index)){
        lastN=lastN.next
    }
    lastN

  }

  override def delete(index: Int): T = {
    rangeCheck(index)
    var oldNode:Node[T] = null
    if(index==0){
      oldNode=n
      n=n.next
    }else{
      val lastNode = findNode(index-1)
      oldNode=lastNode.next
      lastNode.next=oldNode.next
    }
    size0-=1
    oldNode.ele
  }

  override def get(index: Int): T = {
    rangeCheck(index)
    findNode(index).ele
  }

  override def clear(): Unit = {
    n=null
    size0=0
  }

  def rangeCheck(index: Int): Unit = {
    if (index < 0 || index >= size0) {
      throw new IndexOutOfBoundsException("index out of bound !!!")
    }
  }

  def rangeCheckForAdd(index: Int): Unit = {
    if (index < 0 || index > size0) {
      throw new IndexOutOfBoundsException("index out of bound !!!")
    }
  }

  override def toString: String = {

    val sb=new StringBuilder
    var lastN=Node(null.asInstanceOf[T],n)
    for(i <- (0 until size0))  {
      sb.append(lastN.next.ele)
      lastN=lastN.next
    }
    sb.toString()
  }

}

object LinkedList{


  def apply[T](): LinkedList[T] = new LinkedList()

  def main(args: Array[String]): Unit = {


    val l=LinkedList[String]
    l.add("a")
    l.add("b")
    l.add("c")
    l.add("d")
    l.delete(2)
    l.set("b",2)
    l.add("b",2)
    println(l)

  }

}